import random
from copy import deepcopy
import numpy as np


def caculatedistance(distance_matrix, order):
    distancesum = 0.0
    for num in range(len(order)):
        distancesum += distance_matrix[order[num] + 1, order[(num + 1) % (len(order))] + 1]
    return distancesum


class GA:
    def __init__(self, data, crossrate=0.7, mutationrate=0.02, populationsize=None, selectiontype='WES',
                 crossovertype='PMX', mutationtype='swap', parameter=999, scoretype='sum', localsearch=False):
        self.cities = data.cities
        self.city_x, self.city_y = data.x[1:], data.y[1:]
        self.n = len(self.cities)
        self.Distance = data.distance_matrix
        self.crossrate = crossrate  # 交叉概率
        self.mutationrate = mutationrate  # 突变概率
        self.populationsize = int(self.n / 10) + 10 if populationsize is None else populationsize
        self.genelength = len(self.cities)  # 城市数量
        self.population = []  # 种群
        self.best = None  # 保存这一代中最好的个体
        self.evolve_list = []
        self.generation = 1  # 一开始的是第一代
        self.crosscount = 0  # 一开始还没交叉过，所以交叉次数是0
        self.mutationcount = 0  # 一开始还没变异过，所以变异次数是0
        self.bounds = 0.0  # 适配值之和，用于选择时计算概率
        self.selectiontype = selectiontype
        self.crossovertype = crossovertype
        self.mutationtype = mutationtype
        self.parameter = parameter
        self.scoretype = scoretype
        self.localsearch = localsearch
        self.eval = 0
        self.offspringpop, self.parentpop, self.grandparentpop = [], [], []
        self.initpopulation()  # 初始化种群
        # print('POP:', self.populationsize, ' Pc:', self.crossrate, ' Pm', self.mutationrate)

    class aindividual(object):
        def __init__(self, agene=None):
            self.gene = agene
            self.score = -1

        def drawroute(self, data, plt, salesmannum=1, show_text=False):
            route = deepcopy(self.gene)
            for k in range(len(route)):
                route[k] += 1
            route.append(route[0])
            print('\nbestroute:', route)
            data.draw(plt, route=route, show_text=show_text)

    def initpopulation(self):
        self.population = []
        for i in range(self.populationsize):
            gene = list(range(self.genelength))
            random.shuffle(gene)
            individual = self.aindividual(gene)
            self.population.append(individual)
        self.salesmannum = 1

    def judge(self):
        self.chooseselection()
        self.bounds = 0.0  # 适配值之和，用于选择时计算概率
        self.best.score = 1.0 / self.caculatescore(self.best)
        for individual in self.population:
            individual.score = 1.0 / self.caculatescore(individual)
            self.bounds += individual.score
            if self.best.score < individual.score:  # 如果新基因的适配值大于原先的best基因，就更新best基因
                self.best = deepcopy(individual)

    def caculatescore(self, individual):
        self.eval += 1
        return self.distance(individual)

    def distance(self, individual):
        return caculatedistance(self.Distance, individual.gene)

    def multidistance(self, target):
        sums = 0
        for oneroute in target:
            sums = sums + caculatedistance(self.Distance, oneroute)
        return sums

    def amend(self, route1, route2, low, high):
        mapping1 = dict()
        mapping2 = dict()
        for i in range(low, high):
            mapping2[route2[i]] = route1[i]
            mapping1[route1[i]] = route2[i]
        for i in range(low):
            while route1[i] in route1[low:high]:
                route1[i] = mapping1[route1[i]]
            while route2[i] in route2[low:high]:
                route2[i] = mapping2[route2[i]]
        for i in range(high, len(route1)):
            while route1[i] in route1[low:high]:
                route1[i] = mapping1[route1[i]]
            while route2[i] in route2[low:high]:
                route2[i] = mapping2[route2[i]]
        return route1, route2

    def PMX(self, parent1, parent2):
        index1 = random.randint(0, self.genelength - 1)
        index2 = random.randint(index1, self.genelength - 1)
        child1 = parent1[0:index1] + parent2[index1:index2] + parent1[index2:self.genelength]
        child2 = parent2[0:index1] + parent1[index1:index2] + parent2[index2:self.genelength]
        child1, child2 = self.amend(child1, child2, index1, index2)
        return child1, child2

    def CX(self, parent1, parent2):
        child1, child2 = [-1 for i in range(self.genelength)], [-1 for i in range(self.genelength)]
        oripoint = random.randint(0, self.genelength - 1)
        point = oripoint
        child1[point], child2[point] = parent1[point], parent2[point]
        for position in range(self.genelength):
            if parent1[position] == parent2[point]:
                point = position
                break
        while not (point == oripoint):
            child1[point], child2[point] = parent1[point], parent2[point]
            for position in range(self.genelength):
                if parent1[position] == parent2[point]:
                    point = position
                    break
        for position in range(self.genelength):
            if child1[position] == -1:
                child1[position], child2[position] = parent2[position], parent1[position]
        return child1, child2

    def OX(self, parent1, parent2):
        index1 = random.randint(0, self.genelength - 1)
        index2 = random.randint(index1, self.genelength - 1)
        child1 = [-1 for i in range(index1)] + parent1[index1:index2] + [-1 for i in range(self.genelength - index2)]
        child2 = [-1 for i in range(index1)] + parent2[index1:index2] + [-1 for i in range(self.genelength - index2)]
        position1, position2 = 0, 0
        while (position1 < self.genelength) and (position2 < self.genelength):
            if parent2[position1] not in child1:
                if child1[position2] == -1:
                    child1[position2] = parent2[position1]
                else:
                    position2 += 1
            else:
                position1 += 1
        position1, position2 = 0, 0
        while (position1 < self.genelength) and (position2 < self.genelength):
            if parent1[position1] not in child2:
                if child2[position2] == -1:
                    child2[position2] = parent1[position1]
                else:
                    position2 += 1
            else:
                position1 += 1
        return child1, child2

    def PBX(self, parent1, parent2):
        choice = [random.randint(0, 1) for i in range(self.genelength)]
        child1, child2 = [-1 for i in range(self.genelength)], [-1 for i in range(self.genelength)]
        for position in range(self.genelength):
            if choice[position] == 1:
                child1[position], child2[position] = parent1[position], parent2[position]
        position1, position2 = 0, 0
        while (position1 < self.genelength) and (position2 < self.genelength):
            if parent2[position1] not in child1:
                if child1[position2] == -1:
                    child1[position2] = parent2[position1]
                else:
                    position2 += 1
            else:
                position1 += 1
        position1, position2 = 0, 0
        while (position1 < self.genelength) and (position2 < self.genelength):
            if parent1[position1] not in child2:
                if child2[position2] == -1:
                    child2[position2] = parent1[position1]
                else:
                    position2 += 1
            else:
                position1 += 1
        return child1, child2

    def SEX(self, parent1, parent2):
        index1 = random.randint(0, self.genelength - 1)
        index2 = random.randint(index1, self.genelength - 1)
        child1, child2 = parent1, parent2
        exchange1, exchange2 = parent1[index1:index2], []
        for gene in parent2:
            if gene in exchange1:
                exchange2.append(gene)
        position = 0
        for gene in range(self.genelength):
            if child2[gene] in exchange1:
                child2[gene] = exchange1[position]
                position += 1
        position = 0
        for gene in range(self.genelength):
            if child1[gene] in exchange2:
                child1[gene] = exchange2[position]
                position += 1
        return child1, child2

    def OBX(self, parent1, parent2):
        choice = [random.randint(0, 1) for i in range(self.genelength)]
        choice1, choice2 = [], []
        child1, child2 = parent2, parent1
        for position in range(self.genelength):
            if choice[position] == 1:
                choice1.append(parent1[position])
                choice2.append(parent2[position])
        choice01, choice02 = deepcopy(choice1), deepcopy(choice2)
        position = 0
        while not choice1 == []:
            if child1[position] in choice01:
                child1[position] = choice1[0]
                choice1.remove(choice1[0])
            position += 1
        position = 0
        while not choice2 == []:
            if child2[position] in choice02:
                child2[position] = choice2[0]
                choice2.remove(choice2[0])
            position += 1
        return child1, child2

    def GSX(self, parent1, parent2):
        choice = random.randint(0, self.genelength - 1)
        position1, position2 = parent1.index(choice), parent2.index(choice)
        child1, child2, position = [choice], [choice], 0
        while len(child1) < self.genelength:
            if position % 2 == 0:
                while parent1[position1] in child1:
                    position1 = (position1 + 1) % self.genelength
                child1.append(parent1[position1])
            else:
                while parent2[position2] in child1:
                    position2 = (position2 + self.genelength - 1) % self.genelength
                child1.insert(0, parent2[position2])
            position += 1
        position1, position2, position = parent1.index(choice), parent2.index(choice), 0
        while len(child2) < self.genelength:
            if position % 2 == 1:
                while parent1[position1] in child2:
                    position1 = (position1 + 1) % self.genelength
                child2.append(parent1[position1])
            else:
                while parent2[position2] in child2:
                    position2 = (position2 + self.genelength - 1) % self.genelength
                child2.insert(0, parent2[position2])
            position += 1
        return child1, child2

    def APX(self, parent1, parent2):
        child1, child2, position = [], [], 0
        while len(child1) < self.genelength:
            if parent1[position] not in child1:
                child1.append(parent1[position])
            if parent2[position] not in child1:
                child1.append(parent2[position])
            position += 1
        position = 0
        while len(child2) < self.genelength:
            if parent2[position] not in child2:
                child2.append(parent2[position])
            if parent1[position] not in child2:
                child2.append(parent1[position])
            position += 1
        return child1, child2

    def ERX(self, parent1, parent2):
        edgelist, edgecount = [[] for i in range(len(parent1))], []
        for position in range(self.genelength):
            if parent1[(position + 1) % self.genelength] not in edgelist[parent1[position]]:
                edgelist[parent1[position]].append(parent1[(position + 1) % self.genelength])
            if parent1[(position + self.genelength - 1) % self.genelength] not in edgelist[parent1[position]]:
                edgelist[parent1[position]].append(parent1[(position + self.genelength - 1) % self.genelength])
            if parent2[(position + 1) % self.genelength] not in edgelist[parent2[position]]:
                edgelist[parent2[position]].append(parent2[(position + 1) % self.genelength])
            if parent2[(position + self.genelength - 1) % self.genelength] not in edgelist[parent2[position]]:
                edgelist[parent2[position]].append(parent2[(position + self.genelength - 1) % self.genelength])
        for position in range(self.genelength):
            edgecount.append(len(edgelist[position]))
        choice = random.randint(0, self.genelength - 1)
        child = [choice]
        rank = 0
        while len(child) < self.genelength:
            nextchoice = self.listmin(edgecount, edgelist[choice], rank)
            if nextchoice == 999:
                break
            if nextchoice in child:
                rank += 1
            else:
                edgelist = self.removeall(edgelist, [choice])
                choice = nextchoice
                child.append(choice)
                rank = 0
        position = 0
        while len(child) < self.genelength:
            if parent1[position] not in child:
                child.append(parent1[position])
            position += 1
        return child

    def removeall(self, a, e):
        b = []
        for ee in a:
            if ee not in e:
                b.append(ee)
            else:
                continue
        return b

    def listmin(self, targetlist, target, rank):
        if rank < len(target):
            random.shuffle(target)
            sumlist = []
            for i in target:
                sumlist.append(targetlist[i])
            sortlist = sorted(sumlist)
            outcome = sumlist.index(sortlist[rank])
            return target[outcome]
        else:
            return 999

    def MPX(self, parent1, parent2):
        if self.genelength > 20:
            choice = random.randint(10, int(self.genelength / 2))
        else:
            choice = random.randint(1, int(self.genelength / 2))
        index = random.randint(0, self.genelength - choice - 1)
        child1 = [-1 for i in range(index)] + parent1[index:index + choice] + [-1 for i in
                                                                               range(self.genelength - index - choice)]
        child2 = [-1 for i in range(index)] + parent2[index:index + choice] + [-1 for i in
                                                                               range(self.genelength - index - choice)]
        position1, position2 = 0, 0
        while (position1 < self.genelength) and (position2 < self.genelength):
            if parent2[position1] not in child1:
                if child1[position2] == -1:
                    child1[position2] = parent2[position1]
                else:
                    position2 += 1
            else:
                position1 += 1
        position1, position2 = 0, 0
        while (position1 < self.genelength) and (position2 < self.genelength):
            if parent1[position1] not in child2:
                if child2[position2] == -1:
                    child2[position2] = parent1[position1]
                else:
                    position2 += 1
            else:
                position1 += 1
        return child1, child2

    def ULX(self, parent1, parent2):
        child1, child2, rest1, rest2 = [-1 for i in range(self.genelength)], [-1 for i in
                                                                              range(self.genelength)], [], []
        for position in range(self.genelength):
            if parent1[position] == parent2[position]:
                child1[position] = parent1[position]
                child2[position] = parent1[position]
        for city in parent1:
            if city not in child1:
                rest1.append(city)
                rest2.append(city)
        position = 0
        while not rest1 == []:
            if child1[position] == -1:
                if parent1[position] not in child1 and parent2[position] not in child1:
                    flag = lambda x: parent1[position] if random.randint(0, 1) else parent2[position]
                    choice = flag(0)
                elif parent1[position] not in child1:
                    choice = parent1[position]
                elif parent2[position] not in child1:
                    choice = parent2[position]
                else:
                    choice = random.choice(rest1)
                child1[position] = choice
                rest1.remove(choice)
                position += 1
            else:
                position += 1
        position = self.genelength - 1
        while not rest2 == []:
            if child2[position] == -1:
                if parent1[position] not in child2 and parent2[position] not in child2:
                    flag = lambda x: parent1[position] if random.randint(0, 1) else parent2[position]
                    choice = flag(0)
                elif parent1[position] not in child2:
                    choice = parent1[position]
                elif parent2[position] not in child2:
                    choice = parent2[position]
                else:
                    choice = random.choice(rest2)
                child2[position] = choice
                rest2.remove(choice)
                position -= 1
            else:
                position -= 1
        return child1, child2

    def EXX(self, parent1, parent2):
        i1, count = random.randint(0, len(parent1) - 1), 0
        ori = i1
        child1, child2 = parent1, parent2
        while (parent1 == child1) and (count < len(parent1)):
            edge1, edge2 = [], []
            for position in range(self.genelength):
                edge1.append([parent1[position], parent1[(position + 1) % self.genelength]])
                edge2.append([parent2[position], parent2[(position + 1) % self.genelength]])
            i1 = (ori + count) % self.genelength
            for position in range(self.genelength):
                if parent2[position] == parent1[i1]:
                    i2 = position
                    break
            edge1[i1], edge2[i2] = deepcopy(edge2[i2]), deepcopy(edge1[i1])
            while not edge1[i1][1] == edge2[i2][1]:
                for position in range(self.genelength):
                    if edge1[position][0] == edge1[i1][1]:
                        j1 = position
                        break
                for position in range(self.genelength):
                    if edge2[position][0] == edge2[i2][1]:
                        j2 = position
                        break
                for position in range(int(((j1 + self.genelength - i1) % self.genelength + 1) / 2) - 1):
                    edge1[(i1 + position + 1) % self.genelength], edge1[
                        (j1 + self.genelength - position - 1) % self.genelength] = deepcopy(
                        edge1[(j1 + self.genelength - position - 1) % self.genelength]), deepcopy(
                        edge1[(i1 + position + 1) % self.genelength])
                for position in range(i1 + 1, (j1 + self.genelength - i1) % self.genelength + i1):
                    edge1[position % self.genelength][0], edge1[position % self.genelength][1] = \
                        edge1[position % self.genelength][1], edge1[position % self.genelength][0]
                for position in range(int(((j2 + self.genelength - i2) % self.genelength + 1) / 2) - 1):
                    edge2[(i2 + position + 1) % self.genelength], edge2[
                        (j2 + self.genelength - position - 1) % self.genelength] = deepcopy(
                        edge2[(j2 + self.genelength - position - 1) % self.genelength]), deepcopy(
                        edge2[(i2 + position + 1) % self.genelength])
                for position in range(i2 + 1, (j2 + self.genelength - i2) % self.genelength + i2):
                    edge2[position % self.genelength][0], edge2[position % self.genelength][1] = \
                        edge2[position % self.genelength][1], edge2[position % self.genelength][0]
                i1, i2 = j1, j2
                edge1[i1], edge2[i2] = deepcopy(edge2[i2]), deepcopy(edge1[i1])
            child1, child2 = [], []
            for position in range(self.genelength):
                child1.append(edge1[position][0])
                child2.append(edge2[position][0])
            count += 1
        return child1, child2

    def HX(self, parent1, parent2):
        edgelist = [[] for i in range(self.genelength)]
        for position in range(self.genelength):
            if parent1[(position + 1) % self.genelength] not in edgelist[parent1[position]]:
                edgelist[parent1[position]].append(parent1[(position + 1) % self.genelength])
            if parent1[(position + self.genelength - 1) % self.genelength] not in edgelist[parent1[position]]:
                edgelist[parent1[position]].append(parent1[(position + self.genelength - 1) % self.genelength])
            if parent2[(position + 1) % self.genelength] not in edgelist[parent2[position]]:
                edgelist[parent2[position]].append(parent2[(position + 1) % self.genelength])
            if parent2[(position + self.genelength - 1) % self.genelength] not in edgelist[parent2[position]]:
                edgelist[parent2[position]].append(parent2[(position + self.genelength - 1) % self.genelength])
        choice1, choice2 = random.randint(0, self.genelength - 1), random.randint(0, self.genelength - 1)
        rest1, rest2 = list(range(self.genelength)), list(range(self.genelength))
        child1, child2 = [choice1], [choice2]
        while len(child1) < self.genelength:
            rest1.remove(choice1)
            nextchoice = edgelist[choice1][0]
            for edge in edgelist[choice1]:
                if self.Distance[choice1 + 1][edge + 1] < self.Distance[choice1 + 1][nextchoice + 1]:
                    nextchoice = edge
            choice1 = random.choice(rest1) if(nextchoice not in rest1)else nextchoice
            child1.append(choice1)
        while len(child2) < self.genelength:
            rest2.remove(choice2)
            nextchoice = edgelist[choice2][0]
            for edge in edgelist[choice2]:
                if self.Distance[choice2 + 1][edge + 1] < self.Distance[choice2 + 1][nextchoice + 1]:
                    nextchoice = edge
            choice2 = random.choice(rest2) if(nextchoice not in rest2)else nextchoice
            child2.append(choice2)
        return child1, child2

    def SCX(self, parent1, parent2):
        choice = parent1[0]
        self.genelength = len(parent1)
        child1 = [choice]
        rest = list(range(self.genelength))
        rest.remove(choice)
        while len(child1) < self.genelength:
            position1 = parent1.index(choice)
            position2 = parent2.index(choice)
            next1 = parent1[(position1 + 1) % self.genelength] if (
                    parent1[(position1 + 1) % self.genelength] not in child1) else rest[0]
            next2 = parent2[(position2 + 1) % self.genelength] if (
                    parent2[(position2 + 1) % self.genelength] not in child1) else rest[0]
            choice = next1 if(self.Distance[choice + 1][next1 + 1] < self.Distance[choice + 1][next2 + 1])else next2
            child1.append(choice)
            rest.remove(choice)
        choice = parent1[self.genelength - 1]
        child2 = [choice]
        rest = list(range(self.genelength))
        rest.remove(choice)
        while len(child2) < self.genelength:
            position1 = parent1.index(choice)
            position2 = parent2.index(choice)
            next1 = parent1[(position1 - 1) % self.genelength] if (
                    parent1[(position1 - 1) % self.genelength] not in child2) else rest[0]
            next2 = parent2[(position2 - 1) % self.genelength] if (
                    parent2[(position2 - 1) % self.genelength] not in child2) else rest[0]
            choice = next1 if (self.Distance[choice + 1][next1 + 1] < self.Distance[choice + 1][next2 + 1]) else next2
            child2.append(choice)
            rest.remove(choice)
        return child1, child2

    def GNX(self, parent1, parent2, parameter=4):
        index = [0]
        child1, child2 = [-1 for i in range(self.genelength)], [-1 for i in range(self.genelength)]
        for i in range(parameter):
            index.append(random.randint(index[-1] + 1, self.genelength - parameter - 1 + i))
        index.append(self.genelength - 1)
        for i in range(parameter + 1):
            if i % 2 == 0:
                child1[index[i]:index[i + 1]] = parent1[index[i]:index[i + 1]]
                child2[index[i]:index[i + 1]] = parent2[index[i]:index[i + 1]]
        for position in range(self.genelength):
            if child1[position] == -1:
                if parent2[position] not in child1:
                    child1[position] = parent2[position]
            if child2[position] == -1:
                if parent1[position] not in child2:
                    child2[position] = parent1[position]
        rest1, rest2, citylist, position = [], [], list(range(len(parent1))), 0
        random.shuffle((citylist))
        for city in citylist:
            if city not in child1:
                rest1.append(city)
            if city not in child2:
                rest2.append(city)
        while not rest1 == []:
            if child1[position] == -1:
                child1[position] = rest1[0]
                rest1.remove(rest1[0])
            position += 1
        position = 0
        while not rest2 == []:
            if child2[position] == -1:
                child2[position] = rest2[0]
                rest2.remove(rest2[0])
            position += 1
        return child1, child2

    def ZX(self, city_x, city_y, parent1, parent2):
        alpha = random.uniform(0.1, 0.8)
        Lx, Ly = (max(city_x) - min(city_x)) * alpha, (max(city_y) - min(city_y)) * alpha
        choice = random.randint(0, len(parent1) - 1)
        midx, midy = city_x[choice], city_y[choice]
        # midx, midy = (max(city_x) + min(city_x)) / 2, (max(city_y) + min(city_y)) / 2
        flag = []
        for position in range(len(parent1)):
            if abs(city_x[position] - midx) < Lx / 2 and abs(city_y[position] - midy) < Ly / 2:
                flag.append(True)
            else:
                flag.append(False)
        offspring1, offspring2, child = deepcopy([parent1]), deepcopy([parent2]), [[], []]
        for position in range(len(parent1) - 1):
            if flag[parent1[position]] ^ flag[parent1[position + 1]]:
                offspring1.append(parent1[position + 1:])
                for i in range(len(offspring1[-1])):
                    offspring1[-2].remove(offspring1[-1][i])
        if flag[parent1[-1]] ^ flag[parent1[0]] == 0:
            offspring1[-1] = offspring1[-1] + offspring1[0]
            offspring1 = offspring1[1:]
        for position in range(len(parent1) - 1):
            if flag[parent2[position]] ^ flag[parent2[position + 1]]:
                offspring2.append(parent2[position + 1:])
                for i in range(len(offspring2[-1])):
                    offspring2[-2].remove(offspring2[-1][i])
        if flag[parent2[-1]] ^ flag[parent2[0]] == 0:
            offspring2[-1] = offspring2[-1] + offspring2[0]
            offspring2 = offspring2[1:]
        for i in range(len(offspring1)):
            if flag[offspring1[i][0]]:
                child[0].append(offspring1[i])
            else:
                child[1].append(offspring1[i])
        for i in range(len(offspring2)):
            if flag[offspring2[i][0]]:
                child[1].append(offspring2[i])
            else:
                child[0].append(offspring2[i])
        for num in range(2):
            while len(child[num]) > 1:
                target, flag = 1, False
                for i in range(1, len(child[num])):
                    if self.Distance[child[num][i][0] + 1][child[num][0][-1] + 1] < \
                            self.Distance[child[num][target][0] + 1][child[num][0][-1] + 1]:
                        target = i
                for i in range(1, len(child[num])):
                    if not flag:
                        if self.Distance[child[num][i][-1] + 1][child[num][0][-1] + 1] < \
                                self.Distance[child[num][target][0] + 1][child[num][0][-1] + 1]:
                            target = i
                    else:
                        if self.Distance[child[num][i][-1] + 1][child[num][0][-1] + 1] < \
                                self.Distance[child[num][target][-1] + 1][child[num][0][-1] + 1]:
                            target = i
                if flag:
                    child[num][0] = child[num][0] + reversed(child[num][target])
                else:
                    child[num][0] = child[num][0] + child[num][target]
                child[num].remove(child[num][target])
            child[num] = child[num][0]
        return child[0], child[1]

    def edgestoroute(self, edges):
        route, belongs = [], []
        while len(edges) > 0:
            belongs.append(edges[0][-1])
            route.append(edges[0][0:2])
            edges.remove(edges[0])
            while route[-1][-1] != route[-1][0]:
                for edge in edges:
                    if route[-1][-1] in edge:
                        route[-1].append(edge[1 - edge.index(route[-1][-1])])
                        edges.remove(edge)
                        break
        for i in range(len(route)):
            route[i] = [route[i][0:len(route[i]) - 1], belongs[i]]
        return route

    def routetoedges(self, routes):
        edges = []
        for route in routes:
            for i in range(len(route[0])):
                if route[-1] == 'p1':
                    belongs = 'p2' if i % 2 else 'p1'
                else:
                    belongs = 'p1' if i % 2 else 'p2'
                edges.append([route[0][i], route[0][(i + 1) % len(route[0])], belongs])
        return edges

    def edgestoABroute(self, edges):
        route, belongs = [], []
        while len(edges) > 0:
            flag = 1 if edges[0][-1] == 'p1' else 0  # 0 stands for p1 and 1 stands for p2
            belongs.append(edges[0][-1])
            route.append(edges[0][0:2])
            edges.remove(edges[0])
            while route[-1][-1] != route[-1][0] or (len(route[-1]) % 2 == 0):
                for edge in edges:
                    if route[-1][-1] in edge and ((edge[-1] == 'p1') ^ flag):
                        route[-1].append(edge[1 - edge.index(route[-1][-1])])
                        edges.remove(edge)
                        flag = 1 - flag
                        break
        for i in range(len(route)):
            route[i] = [route[i][0:len(route[i]) - 1], belongs[i]]
        return route

    def decreasecircle(self, circle):
        rk = [caculatedistance(self.Distance, i) for i in circle]
        rk = circle[rk.index(min(rk))]
        circle.remove(rk)
        besta, bestb, bestroute = 0, 0, 0
        best = self.Distance[rk[0] + 1][rk[1] + 1] + self.Distance[circle[0][0] + 1][circle[0][1] + 1] - \
               self.Distance[rk[0] + 1][circle[0][0] + 1] - self.Distance[rk[1] + 1][circle[0][1] + 1]
        pflag = 0
        for a in range(len(rk)):
            for route in range(len(circle)):
                for b in range(len(circle[route])):
                    temp = self.Distance[rk[a] + 1][rk[(a + 1) % len(rk)] + 1] + \
                           self.Distance[circle[route][b] + 1][circle[route][(b + 1) % len(circle[route])] + 1] - \
                           self.Distance[rk[a] + 1][circle[route][b] + 1] - \
                           self.Distance[rk[(a + 1) % len(rk)] + 1][
                               circle[route][(b + 1) % len(circle[route])] + 1]
                    if temp > best:
                        best, besta, bestb, bestroute = temp, a, b, route
        rk = rk[::-1]
        for a in range(len(rk)):
            for route in range(len(circle)):
                for b in range(len(circle[route])):
                    temp = self.Distance[rk[a]][rk[(a + 1) % len(rk)]] + \
                           self.Distance[circle[route][b]][circle[route][(b + 1) % len(circle[route])]] - \
                           self.Distance[rk[a]][circle[route][b]] - \
                           self.Distance[rk[(a + 1) % len(rk)]][circle[route][(b + 1) % len(circle[route])]]
                    if temp > best:
                        pflag = 1
                        best, besta, bestb, bestroute = temp, a, b, route
        if not pflag:
            rk = rk[::-1]
        rk = rk[besta + 1:] + rk[:besta + 1] if (besta + 1) % len(rk) else rk
        circle[bestroute] = circle[bestroute][bestb + 1:] + circle[bestroute][:bestb + 1] \
            if (bestb + 1) % len(circle[bestroute]) else circle[bestroute]
        circle[bestroute] = circle[bestroute] + rk[::-1]
        return circle

    def EAX(self, parent1, parent2):
        choice = random.randint(0, self.genelength - 1)
        parent1 = parent1[parent1.index(choice):] + parent1[:parent1.index(choice)]
        parent2 = parent2[parent2.index(choice):] + parent2[:parent2.index(choice)]
        edge1 = [[parent1[i], parent1[(i + 1) % self.genelength], 'p1'] for i in range(self.genelength)]
        edge2 = [[parent2[i], parent2[(i + 1) % self.genelength], 'p2'] for i in range(self.genelength)]
        Aset, Bset = [], []
        for i in range(self.genelength):
            if i % 2:
                Bset.append(edge1[i])
                Bset.append(edge2[i])
            else:
                Aset.append(edge1[i])
                Aset.append(edge2[i])
        ABset = self.edgestoABroute(Aset) + self.edgestoABroute(Bset)
        Eset = self.removeall([i if len(i[0]) > 2 and random.random() > 0.5 else [] for i in ABset], [[]])
        Esetedges = self.routetoedges(Eset)
        offedge1, offedge2 = deepcopy(edge1), deepcopy(edge2)
        for edge in Esetedges:
            if edge[-1] == 'p1':
                if edge in offedge1:
                    offedge1.remove(edge)
                else:
                    offedge1.remove(edge[0:2][::-1] + [edge[-1]])
                offedge2.append(edge)
            else:
                if edge in offedge2:
                    offedge2.remove(edge)
                else:
                    offedge2.remove(edge[0:2][::-1] + [edge[-1]])
                offedge1.append(edge)
        offedge1, offedge2 = self.edgestoroute(offedge1), self.edgestoroute(offedge2)
        off = [[i[0] for i in offedge1], [i[0] for i in offedge2]]
        for num in range(len(off)):
            while len(off[num]) > 1:
                off[num] = self.decreasecircle(off[num])
        return off[0][0], off[1][0]

    def choosecrossover(self, parent1, parent2):
        if self.crossovertype == 'PMX':
            child1, child2 = self.PMX(parent1, parent2)
        elif self.crossovertype == 'OX':
            child1, child2 = self.OX(parent1, parent2)
        elif self.crossovertype == 'CX':
            child1, child2 = self.CX(parent1, parent2)
        elif self.crossovertype == 'PBX':
            child1, child2 = self.PBX(parent1, parent2)
        elif self.crossovertype == 'SEX':
            child1, child2 = self.PBX(parent1, parent2)
        elif self.crossovertype == 'OBX':
            child1, child2 = self.OBX(parent1, parent2)
        elif self.crossovertype == 'GSX':
            child1, child2 = self.GSX(parent1, parent2)
        elif self.crossovertype == 'APX':
            child1, child2 = self.APX(parent1, parent2)
        elif self.crossovertype == 'ERX':
            child1 = self.ERX(parent1, parent2)
            child2 = self.ERX(parent1, parent2)
        elif self.crossovertype == 'MPX':
            child1, child2 = self.MPX(parent1, parent2)
        elif self.crossovertype == 'ULX':
            child1, child2 = self.ULX(parent1, parent2)
        elif self.crossovertype == 'EXX':
            child1, child2 = self.EXX(parent1, parent2)
        elif self.crossovertype == 'HX':
            child1, child2 = self.HX(parent1, parent2)
        elif self.crossovertype == 'SCX':
            child1, child2 = self.SCX(parent1, parent2)
        elif self.crossovertype == 'GNX':
            if self.parameter == 999:
                child1, child2 = self.GNX(parent1, parent2)
            else:
                child1, child2 = self.GNX(parent1, parent2, self.parameter)
        elif self.crossovertype == 'ZX':
            child1, child2 = self.ZX(self.city_x, self.city_y, parent1, parent2)
        elif self.crossovertype == 'EAX':
            child1, child2 = self.EAX(parent1, parent2)
        else:
            raise TypeError('undefined crossover')
        self.crosscount += 1
        return child1, child2

    def choosemutation(self, gene):
        if self.mutationtype == 'swap':
            gene = self.swap(gene)
        elif self.mutationtype == 'twoopt':
            gene = self.twoopt(gene)
        elif self.mutationtype == 'shuffle1':
            gene = self.shuffle1(gene)
        elif self.mutationtype == 'shuffle2':
            gene = self.shuffle2(gene)
        elif self.mutationtype == 'insert':
            gene = self.insert(gene)
        else:
            raise TypeError('undefined mutation')
        self.mutationcount += 1
        return gene

    def chooseselection(self):
        if self.selectiontype == 'WES':
            self.WES()
        elif self.selectiontype == 'POES':
            self.POES()
        elif self.selectiontype == 'CGES':
            self.CGES()
        else:
            raise TypeError('undefined selection')

    def WES(self):
        pass

    def POES(self):
        self.parentpop = self.offspringpop
        self.offspringpop = self.population
        self.population = self.population + self.parentpop

    def CGES(self):
        self.grandparentpop = self.parentpop
        self.parentpop = self.offspringpop
        self.offspringpop = self.population
        self.population = self.population + self.grandparentpop

    def swap(self, gene):
        genelen = len(gene)
        index1 = random.randint(0, genelen - 1)
        index2 = random.randint(0, genelen - 1)
        gene[index1], gene[index2] = gene[index2], gene[index1]
        return gene

    def twoopt(self, gene):
        index1 = random.randint(0, len(gene))
        index2 = random.randint(index1, len(gene))
        gene[index1:index2] = gene[index1:index2][::-1]
        return gene

    def shuffle1(self, gene):
        index1, index2 = 0, 0
        genelen = len(gene)
        while index1 == index2:
            index1 = random.randint(0, genelen - 1)
            index2 = random.randint(0, genelen - 1)
        genelist = []
        for position in range((index2 - index1 + genelen) % genelen):
            genelist.append(gene[(index1 + position) % genelen])
        random.shuffle(genelist)
        for position in range((index2 - index1 + genelen) % genelen):
            gene[(index1 + position) % genelen] = genelist[position]
        return gene

    def insert(self, gene):
        genelen = len(gene)
        index1, index2 = random.randint(0, genelen - 1), random.randint(0, genelen - 1)
        temp = gene[index1]
        gene.remove(temp)
        gene.insert(index2, temp)
        return gene

    def shuffle2(self, gene):
        genelen = len(gene)
        shufflelist = [random.randint(0, 1) for i in range(genelen)]
        genelist, listposition = [], 0
        for position in range(genelen):
            if shufflelist[position]:
                genelist.append(gene[position])
        random.shuffle(genelist)
        position = 0
        while listposition < len(genelist):
            if shufflelist[position]:
                gene[position] = genelist[listposition]
                position, listposition = position + 1, listposition + 1
            else:
                position += 1
        return gene

    def selection(self):
        self.population.sort(key=lambda x: x.score, reverse=True)
        populationnew = [deepcopy(self.best), self.population[0]]
        #populationnew = [deepcopy(self.best)]
        prob = [self.population[i].score / self.bounds for i in range(len(self.population))]
        while len(populationnew) < self.populationsize:
            populationnew.append(np.random.choice(self.population, replace=True, p=prob))
        self.population = populationnew

    def crossover(self):
        populationnew = []
        random.shuffle(self.population)
        for i in range(int(self.populationsize / 2)):
            rate = random.random()
            if rate < self.crossrate:
                parent1 = self.population[i * 2]
                parent2 = self.population[i * 2 + 1]
                child1, child2 = self.choosecrossover(parent1.gene, parent2.gene)
                child1, child2 = self.aindividual(child1), self.aindividual(child2)
            else:
                child1 = self.population[i * 2]
                child2 = self.population[i * 2 + 1]
            populationnew.append(child1)
            populationnew.append(child2)
        while len(populationnew) < self.populationsize:
            populationnew.append(self.population[-1])
        self.population = populationnew

    def mutation(self):
        for i in range(self.populationsize):
            rate = random.random()  # 按概率突变
            if rate < self.mutationrate:
                self.population[i].gene = self.choosemutation(self.population[i].gene)

    def LStwoopt(self, route):
        best = caculatedistance(self.Distance, route)
        flag = True
        while flag:
            flag = False
            for index1 in range(len(route)):
                for index2 in range(index1, len(route)):
                    temp = deepcopy(route)
                    temp[index1:index2] = temp[index1:index2][::-1]
                    if caculatedistance(self.Distance, temp) < best:
                        route = temp
                        best = caculatedistance(self.Distance, temp)
                        flag = True
        return route

    def LocalSearch(self, localsearch=False):
        if self.localsearch or localsearch:
            self.best.gene = self.LStwoopt(self.best.gene)

    def newgeneration(self):
        self.selection()
        self.crossover()
        self.mutation()
        self.generation += 1
        self.judge()

    def optimize(self, evalset=None, genset=None, display=True):
        self.best = deepcopy(self.population[0])
        self.judge()
        if evalset is None:
            evalset = self.n * 1000
        while self.eval <= evalset:
            self.newgeneration()
            bestroutedistance = self.distance(self.best)
            self.evolve_list.append(bestroutedistance)
            if display:
                print('\r', self.generation, ' ', bestroutedistance, ' ', self.best.score, end='')
            if genset is not None and self.generation >= genset:
                break
        self.LocalSearch()
        return self.best

